package 排序算法;

/**
 * 插入排序：
 * 从左到右取出每一个数据不断的与自己左边的每个数据进行对比，选择一个适合自己插入的位置插入
 */
public class 插入排序 {

    public static void main(String[] args) {
        Integer[] arrays = {1, 56, 32, 56, 12, 77, 88, 21};
//        for (int begin = 1; begin < arrays.length; begin++) {
//            int cur = begin;
//            while (cur > 0 && arrays[cur] < arrays[cur - 1]) {
//                int tmp = arrays[cur - 1];
//                arrays[cur - 1] = arrays[cur];
//                arrays[cur] = tmp;
//                cur --;
//            }
//        }

        //优化1：将交换变成挪动，例如：32要挪到1后面，先将32备份，将56向后挪动一格
//        for (int begin = 1; begin < arrays.length; begin++) {
//            int cur = begin;
//            int tmp = arrays[cur];
//            while (cur > 0 && tmp < arrays[cur - 1]) {
//                arrays[cur] = arrays[cur - 1];
//                cur--;
//            }
//
//            arrays[cur] = tmp;
//        }

        //优化2：利用二分搜索减少比较次数
        for (int begin = 1; begin < arrays.length; begin++) {
            int tmp = arrays[begin];
            int searchIndex = search(arrays, begin);
            //挪动位置
            for (int i = begin; i > searchIndex; i--) {
                arrays[i] = arrays[i-1];
            }

            arrays[searchIndex] = tmp;

        }


        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "_");
        }
    }

    /**
     * @param array
     * @param index 已经排好序的区间范围 [0，index)
     * @return
     */
    private static int search(Integer[] array, int index) {
        if (array == null || array.length == 0) return -1;
        int element = array[index];
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (end + begin) >> 1;
            if (element >= array[mid]) {
                begin = mid + 1;
            } else {
                end = mid;
            }
        }

        return begin;
    }

}
